/************************************************************
 * Project Name         [Thinking_In_Java]
 * File Name            [UnrepeatableRandomNumber.java]
 * Creation Date        [02-Jul-2014]
 * 
 * Copyright© ge.y.yang@gmail.com All Rights Reserved
 * 
 * Work hard, play harder, think big and keep fit
 ************************************************************/
package pkg_algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 生成无重复的随机数
 * 
 * @author 不落的太阳(Sean Yang)
 * @version 1.0
 * @since JDK 6
 * 
 */
public class UnrepeatableRandomNumber {

	private int min;
	private int max;

	/**
	 * 构造方法
	 */
	public UnrepeatableRandomNumber() {
		super();
		min = 0;
		max = 10;
	}

	/**
	 * 构造方法
	 * 
	 * @param min
	 * @param max
	 */
	public UnrepeatableRandomNumber(int min, int max) {
		this();
		if (max >= min) {
			this.min = min;
			this.max = max;
		} else {
			System.out.println("max小于min, 按照缺省值生成UnrepeatRandomNumber对象!");
		}
	}

	/**
	 * 排除法 --- 如果是新生成的数字, 则放到结果列表中, 否则是已经生成过的, 则不加入结果列表, 继续随机生成
	 * 
	 * @param length
	 *            结果列表的长度
	 * @return 存放生成的随机数的数组
	 */
	public Integer[] eliminationMethod(int length) {
		if (length <= 0) {
			return new Integer[0];
		} else if (length > (max - min)) {
			System.out.println("结果列表长度不能达到 " + length + " , 结果列表长度只能是 "
					+ (max - min));
			length = max - min;
		}
		java.util.Random random = new java.util.Random();
		List<Integer> resultList = new ArrayList<Integer>();
		while (resultList.size() < length) {
			// 将[min, max]区间等价于min + [0, max - min + 1)
			Integer randomNumber = new Integer(min
					+ random.nextInt(max - min + 1));
			if (!resultList.contains(randomNumber)) {
				resultList.add(randomNumber);
			}
		}
		// 使用toArray方法将List转换成对象数组返回
		return resultList.toArray(new Integer[0]);
	}

	/**
	 * 筛选法 --- 将所有可能被生成的数字放到一个候选列表中, 然后生成随机数, 作为下标, 将候选列表中相应下标的数字放到放到结果列表中, 同时,
	 * 把它在候选列表中删除
	 * 
	 * @param length
	 *            结果列表的长度
	 * @return 存放生成的随机数的数组
	 */
	public Integer[] sieveMethod(int length) {
		if (length <= 0) {
			return new Integer[0];
		} else if (length > (max - min)) {
			System.out.println("结果列表长度不能达到 " + length + " , 结果列表长度只能是 "
					+ (max - min));
			length = max - min;
		}

		// 初始化候选列表, 列表长度为max - min + 1
		int candidateListLength = max - min + 1;
		List<Integer> candidateList = new ArrayList<Integer>();
		for (int i = min; i <= max; i++) {
			candidateList.add(new Integer(i));
		}

		java.util.Random random = new java.util.Random();
		List<Integer> resultList = new ArrayList<Integer>();
		while (resultList.size() < length) {
			// 生成下标, 在[0, candidateListLength)范围内
			int index = random.nextInt(candidateListLength);
			// 将候选队列中下标为index的数字对象放入结果队列
			resultList.add(candidateList.get(index));
			// 将下标为index的数字对象从候选队列中删除
			candidateList.remove(index);
			// 候选队列长度减一
			candidateListLength--;
		}
		// 使用toArray方法将List转换成对象数组返回
		return resultList.toArray(new Integer[0]);
	}

	/**
	 * 测试方法
	 * 
	 * @param args
	 *            命令行参数
	 */
	public static void main(String[] args) {
		UnrepeatableRandomNumber test = new UnrepeatableRandomNumber(5, 15);
		Arrays.toString(test.eliminationMethod(8));
		Arrays.toString(test.sieveMethod(8));
		/*
		 * 第一种方法利用Random对象生成的随机数的次数比较多, 可能生成了20次数字, 才能找到10个不一样的数字
		 * 第二种方法利用Random对象生成的随机数的次数比较少, 需要多少个, 就生成多少个, 保证了每次生成的数字都不重复
		 * 第一种方法在时间花费上更多, 但是第二种方法需要初始化一个候选队列, 需要更多的空间花费
		 */
	}
}
